Leetcode刷题记录(Java)

⭐Problem 257 Binary Tree Paths

该问题属于二叉树遍历问题,需要输出从根到叶子结点的路径,也就是深度优先遍历

---

主要思路:
该题思想比较简单,比较直观的想法就是从根开始遍历,先访问左子树,一直访问到最左边的叶子结点,再访问叶子结点的父节点的右子树,依次递归访问完成遍历。
该题同样分为几种情况:

• 空树
• 单结点
• 多层结点

对于空树直接返回new List即可,对于单结点直接返回结点即可,对于多层结点则有很多需要注意的点,由于题目输出要求1->2->3这种带有箭头的形式,所以我的处理方法是在每个可访问结点之前进行处理,然后在加入list之前统一去掉多余箭头,而其中最重要的一点是递归结束之后的结点回退问题,由于我此处使用的是String,所以在某层遍历结束后,退出时需要清除该层以及下层的信息

---

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<String> paths = new ArrayList<>();
    String path = "";
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null){
            return new ArrayList<String>();
        }
        path += "->"+root.val;
        if(root.left==null&&root.right==null){
            if(path.length()==3){
                paths.add(path.substring(2));
                return paths;
            }
            if(path.startsWith("->")){
                paths.add(path.substring(2));
                String[]  nodes = path.substring(2).split("->");
                path = nodes[0];
                for(int i=1;i<nodes.length-1;i++){
                    path += "->"+nodes[i];
                }
            }else {
                paths.add(path);
                path = eraseUnnecessaryArrow(path);
            }
            return null;
        }
        if(root.left==null){
            binaryTreePaths(root.right);
            path = eraseUnnecessaryArrow(path);
        }else {
            binaryTreePaths(root.left);
            binaryTreePaths(root.right);
            path = eraseUnnecessaryArrow(path);
        }
        return paths;
    }
    public String eraseUnnecessaryArrow(String s){
        String[]  nodes = s.split("->");
        s = nodes[0];
        for(int i=1;i<nodes.length-1;i++){
            s += "->"+nodes[i];
        }
        return s;
    }
}

---

⭐Problem 198 House Robber

该问题简化来说就是求数组中子数组的最大值,但子数组中各个数不能直接相邻

---

代码实现:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n <= 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);
        int[] dirtyMoney = new int[n];
        dirtyMoney[0] = nums[0];
        dirtyMoney[1] = Math.max(nums[0], nums[1]);
        int maxRob = 0;
        for (int i = 2; i < n; i++) {
            dirtyMoney[i] = Math.max(dirtyMoney[i - 1], nums[i] + dirtyMoney[i - 2]);
            if (dirtyMoney[i] > maxRob) maxRob = dirtyMoney[i];
        }
        return maxRob;
    }
}

---

主要思路:
该题是典型的贪心算法的应用,先不考虑极端情况

• 元素为空,返回0
• 元素长度为1,返回当前元素
• 元素长度为2,返回max(元素1,元素2)

而对于其他情况则使用贪心算法,首先设立一个新的数组dirtyMoney,并将dirtyMoney[0]置为nums[0],dirtyMoney[1]置为max(nums[0],nums[1]),而到了dirtyMoney[2],此时它的值面临两个选择,那就是nums[2]是否加入运算.如果它加入,根据目前的情况,相邻数字不能想加,所以其只能加dirtyMoney[i-2]也就是dirtyMoney[0].而如果它不加入的话,则直接采用dirtyMoney[1],随后取两者中的最大值,作为dirtyMoney当前位的值,继续遍历,不断取出局部最大值,最终达到全局最大.

---